Skip to content

Latest commit

 

History

History
131 lines (119 loc) · 4.27 KB

README.md

File metadata and controls

131 lines (119 loc) · 4.27 KB

36. Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] Output: true

Example 2:

Input: [ ["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Solutions (Rust)

1. Solution1

use std::collections::HashSet;implSolution{pubfnis_valid_sudoku(board:Vec<Vec<char>>) -> bool{letmut cnt_row;letmut set_row = HashSet::new();letmut cnt_col = vec![0;9];letmut set_col = vec![HashSet::new();9];letmut cnt_sub = vec![0;3];letmut set_sub = vec![HashSet::new();3];for row in0..9{ cnt_row = 0; set_row.clear();if row % 3 == 0{for i in0..3{ cnt_sub[i] = 0; set_sub[i].clear();}}for col in0..9{if board[row][col] != '.'{ cnt_row += 1; set_row.insert(board[row][col]); cnt_col[col] += 1; set_col[col].insert(board[row][col]); cnt_sub[col / 3] += 1; set_sub[col / 3].insert(board[row][col]);}if col % 3 == 2{if cnt_sub[col / 3] != set_sub[col / 3].len(){returnfalse;}}if row == 8{if cnt_col[col] != set_col[col].len(){returnfalse;}}}if cnt_row != set_row.len(){returnfalse;}}true}}

2. Solution2

implSolution{pubfnis_valid_sudoku(board:Vec<Vec<char>>) -> bool{letmut ans = vec![vec![vec![false;9];3];9];for row in0..9{for col in0..9{let sub = row / 3*3 + col / 3;if board[row][col] != '.'{let n = board[row][col].to_digit(10).unwrap()asusize - 1;if ans[n][0][row] || ans[n][1][col] || ans[n][2][sub]{returnfalse;} ans[n][0][row] = true; ans[n][1][col] = true; ans[n][2][sub] = true;}}}true}}
close